// NC14 按之字形顺序打印二叉树
// deqNode.front()/pop_front()/push_front()
// deqNode.back()/pop_back()/push_back()
// if (deqNode.empty()) break; 否则打印空组

vector<vector<int> > Print(TreeNode* pRoot) {
  vector<vector<int> > res;
  if (pRoot == nullptr) {
    return res;
  }
  deque<TreeNode*> deqNode;
  deqNode.push_front(pRoot);
  while (!deqNode.empty()) {
    vector<int> vtTmp;
    //  print odd
    vtTmp.clear();
    for (int i = deqNode.size(); i > 0; i--) {
      TreeNode* node = deqNode.front();
      deqNode.pop_front();
      vtTmp.push_back(node->val);
      if (node->left) deqNode.push_back(node->left);
      if (node->right) deqNode.push_back(node->right);
    }
    res.push_back(vtTmp);
    if (deqNode.empty()) break;
    //  print even
    vtTmp.clear();
    for (int i = deqNode.size(); i > 0; i--) {
      TreeNode* node = deqNode.back();
      deqNode.pop_back();
      vtTmp.push_back(node->val);
      if (node->right) deqNode.push_front(node->right);
      if (node->left) deqNode.push_front(node->left);
    }
    res.push_back(vtTmp);
  }
  return res;
}
